#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点的函数
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 中序遍历并存储节点值的函数
void inorderTraversal(TreeNode* root, int* arr, int* index) {
    if (root == NULL) return;
    inorderTraversal(root->left, arr, index);
    arr[(*index)++] = root->val;
    inorderTraversal(root->right, arr, index);
}

// 检查数组是否有序的函数
int isSorted(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return 0; // 无序
        }
    }
    return 1; // 有序
}

// 判别二叉树是否为二叉排序树的函数
int isBinarySearchTree(TreeNode* root) {
    int arr[1000]; // 假设数组足够大，可以存储所有节点值
    int index = 0;
    inorderTraversal(root, arr, &index);
    return isSorted(arr, index);
}

int main() {
    // 创建一个示例二叉树
    //       4
    //      / \
    //     2   6
    //    / \ / \
    //   1  3 5  7
    TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    // 检查是否为二叉排序树
    if (isBinarySearchTree(root)) {
        printf("The binary tree is a Binary Search Tree (BST).\n");
    } else {
        printf("The binary tree is NOT a Binary Search Tree (BST).\n");
    }

    return 0;
}
